#include<vector>
#include<stack>
using std::stack;
using std::vector;



struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (!preorder.size()) return nullptr;
        TreeNode* root = new TreeNode(preorder[0]);
        stack<TreeNode*> treeStack;
        treeStack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.size(); i++) {
            auto preOrderValue = preorder[i];
            TreeNode* node = treeStack.top();
            // 如果中序值与栈顶不一致，入栈
            if (inorder[inorderIndex] != treeStack.top()->val) {
                node->left = new TreeNode(preOrderValue);
                treeStack.push(node->left);
            }
            else {

                while (!treeStack.empty() && treeStack.top()->val == inorder[inorderIndex]) {
                    // 遍历该分支（无右子）
                    treeStack.top()->left = node; 
                    node = treeStack.top();
                    treeStack.pop();
                    inorderIndex++;    
                }
                // 不等于时，即遇到第一个有右儿子的祖先
                node->right = new TreeNode(preOrderValue);
                treeStack.push(node->right);
            }
        }
        return root;
    }

   
};